package correct.day4;


import java.util.Scanner;

public class Test2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board string字符串一维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static boolean exist (String[] board, String word) {
        // write code here
        int m = board.length;
        int n = board[0].length();
        boolean[][] dp = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i].charAt(j) == word.charAt(0)) {

                    if (isWord(board, i, j, dp, word, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static boolean isWord(String[] board, int a, int b, boolean[][] dp, String word, int index) {
        if (index == word.length() - 1) {
            return true;
        }
        int m = board.length;
        int n = board[0].length();
        dp[a][b] = true; 
        for(int i = 0; i < 4; i++) {
            int x = a + dx[i];
            int y = b + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x].charAt(y) == word.charAt(index+1) && dp[x][y] == false) {
                if(isWord(board, x, y, dp, word, index+1)) {
                     return true;
                }
            }
        }
        dp[a][b] = false;
        return false;
    }

    // "CAA","AAA","BCD"],"AAB"
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] board = {"CAA","AAA","BCD"};
        String word = "AAB";
        System.out.println(exist(board, word));
    }
}